package org.forever.util
{
	/**
	* 基于双向链表实现列表结构
	*/
	public class List_DLNode implements List
	{
		private var _size:int;//列表的实际规模
		protected var _header:DLNode;//哨兵：首节点+末节点
		protected var _trailer:DLNode;
		
		
		/**构造函数*/
		public function List_DLNode()
		{	
			_size = 0;//空表
			_header = new DLNode(null, null, null);//头节点
			_trailer = new DLNode(null, _header, null);//尾节点
			_header.setNext(_trailer);//头、尾节点相互链接
		}
		
		/**************************** 辅助方法 ****************************/
		/**检查给定位置在列表中是否合法，若是，则将其转换为*DLNode*/
		public function checkPosition(p:Position):DLNode{
			if(null==p){
				throw new Error("异常：传递给List_DLNode的位置是null");
			}
			if(_header==p){
				throw new Error("异常：头节点哨兵位置非法");
			}
			if(_trailer==p){
				throw new Error("异常：尾结点哨兵位置非法");
			}
			return p as DLNode;
		}
		
		
		
		/**************************** ADT方法 ****************************/
		/**查询列表当前的规模*/
		public function getSize():int
		{
			return _size;
		}
		/**判断列表是否为空*/
		public function isEmpty():Boolean
		{
			return _size==0;
		}
		/**返回第一个元素（的位置）*/
		public function first():Position
		{
			if(isEmpty()){
				throw new Error("异常：列表空");
			}
			return _header.getNext();
		}
		
		
		/**返回最后一个元素（的位置）*/
		public function last():Position
		{
			if(isEmpty()){
				throw new Error("异常：列表空");
			}
			return _trailer.getPrev();
		}
		
		/**返回紧靠给定位置之前的元素（的位置）*/
		public function getPrev(p:Position):Position{
			var v:DLNode = checkPosition(p);
			var prev:DLNode = v.getPrev();
			if(prev==_header){
				throw new Error("异常：企图越过列表前端");
			}
			return prev;
		}
		
		/**返回紧接给定位置之后的元素（的位置）*/
		public function getNext(p:Position):Position{
			var v:DLNode = checkPosition(p);
			var next:DLNode = v.getNext();
			if(next == _trailer){
				throw new Error("异常：企图越过列表末端");
			}
			return next;
		}
		
		/**将e作为第一个元素插入列表*/
		public function insertFirst(e:Object):Position
		{
			_size++;
			var newNode:DLNode = new DLNode(e,_header,_header.getNext());
			_header.getNext().setPrev(newNode);
			_header.setNext(newNode);
			return newNode;
		}
		/**将e作为最后一个元素插入列表*/
		public function insertLast(e:Object):Position
		{
			_size++;
			var newNode:DLNode = new DLNode(e,_trailer.getPrev(),_trailer);
			_trailer.getPrev().setNext(newNode);
			_trailer.setPrev(newNode);
			return newNode;
		}
		
		/**将e插入至紧接给定位置之后的位置*/
		public function insertAfter(p:Position, e:Object):Position
		{
			var v:DLNode = checkPosition(p);
			_size++;
			var newNode:DLNode = new DLNode(e,v,v.getNext());
			v.getNext().setPrev(newNode);
			v.setNext(newNode);
			return newNode;
		}
		
		/**将e作为第一个元素插入列表*/
		public function insertBefore(p:Position, e:Object):Position
		{
			var v:DLNode = checkPosition(p);
			_size++;
			var newNode:DLNode = new DLNode(e,v.getPrev(),v);
			v.getPrev().setNext(newNode);
			v.setPrev(newNode);
			return newNode;
		}
		
		/**删除给定位置处的元素，并返回之*/
		public function remove(p:Position):Object
		{
			var v:DLNode = checkPosition(p);
			_size--;
			var vPrev:DLNode = v.getPrev();
			var vNext:DLNode = v.getNext();
			vPrev.setNext(vNext);
			vNext.setPrev(vPrev);
			v.setPrev(null);
			v.setNext(null);
			return v.getElem();
		}
		
		/**删除首元素，并返回之*/
		public function removeFirst():Object
		{
			return remove(first());
		}
		
		/**删除末元素，并返回之*/
		public function removeLast():Object
		{
			return remove(last());
		}
		
		/**将处于给定位置的元素替换为新元素，并返回被替换的元素*/
		public function replace(p:Position, e:Object):Object
		{
			var v:DLNode = checkPosition(p);
			var oldElem:Object = v.getElem();
			v.setElem(e);
			return oldElem;
		}
		
		/**元素迭代器*/
		public function elements():Iterator
		{
			return new IteratorElement(this);
		}
		
		/**元素迭代器*/
		public function positions():Iterator
		{
			return new IteratorPosition(this);
		}

	}
}